[2017_HackCon] [CRYPTO] RSA-2

문제내용

n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381

e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205

c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635

문제 풀이

n과 e로 p, q를 구하는 함수가 있다. 가져다 쓰자.

sage: def factor_rsa_wiener(N, e):
          """Wiener's attack: Factorize the RSA modulus N given the public exponents
          e when d is small.
          Source: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
          CTF: BKP CTF 2016 Bob's Hat
          """
          N = Integer(N)
          e = Integer(e)
          cf = (e / N).continued_fraction().convergents()
          for f in cf:
              k = f.numer()
              d = f.denom()
              if k == 0:
                  continue
              phi_N = ((e * d) - 1) / k
              b = -(N - phi_N + 1)
              dis = b ^ 2 - 4 * N
              if dis.sign() == 1:
                  dis_sqrt = sqrt(dis)
                  p = (-b + dis_sqrt) / 2
                  q = (-b - dis_sqrt) / 2
                  if p.is_integer() and q.is_integer() and (p * q) % N == 0:
                      p = p % N
                      q = q % N
                      if p > q:
                          return (p, q)
                      else:
                          return (q, p)


sage: p,q = factor_rsa_wiener(n, e)
sage: phi = (p-1)*(q-1)

sage: d = inverse_mod(e, phi)

sage: decrypted = Mod(c, n) ** d

sage: flag = hex(Integer(decrypted)).decode('hex')
sage: print(flag)